import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
        printIndexOfArray(arr);
        countingSort(arr);
        printIndexOfArray(arr);
    }

    public static void countingSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int[] count = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }

        int[] output = new int[arr.length];
        int j = 0;
        for (int i = 1; i <= max; i++) {
            while (count[i] > 0) {
                output[j] = i;
                j++;
                count[i]--;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }

        // // Calculate the cumulative sum of the counts
        // for (int i = 1; i <= max; i++) {
        //     count[i] += count[i - 1];
        // }

        // int[] output = new int[arr.length];
        // for (int i = arr.length - 1; i >= 0; i--) {
        //     output[count[arr[i]] - 1] = arr[i];
        //     count[arr[i]]--;
        // }

        // for (int i = 0; i < arr.length; i++) {
        //     arr[i] = output[i];
        // }
    }

    public static void printIndexOfArray(int[] arr) {
        Arrays.stream(arr).mapToObj(i -> i + " ").forEach(System.out::print);
        System.out.println();
    }

}
